#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <sys/time.h>
#include "heap.h"

/* ******************************************************************
 *                      FUNCIONES AUXILIARES
 * *****************************************************************/

/* Función auxiliar para imprimir si estuvo OK o no. */
void print_test(char* name, bool result)
{
    printf("%s: %s\n", name, result? "OK" : "ERROR");
}

/* ******************************************************************
 *                        PRUEBAS UNITARIAS
 * *****************************************************************/


/* Prueba que las primitivas de la lista funcionen correctamente. */
void prueba_crear_heap_vacio()
{
	heap_t* heap = heap_crear(NULL);
	
	print_test("Prueba heap crear heap vacio", heap);
	print_test("Prueba heap la cantidad de elementos es 0", heap_cantidad(heap) == 0);
	print_test("Prueba heap esta vacio es true", heap_esta_vacio(heap));
	print_test("Prueba heap obtener clave A, es NULL, no existe", !heap_ver_max(heap));
	print_test("Prueba heap borrar clave A, es NULL, no existe", !heap_desencolar(heap));

	heap_destruir(heap,NULL);
}


int comparar_max(const int *clave1,const int *clave2){

	if (*clave1<*clave2)
		return -1;
		
	if (*clave1>*clave2)
		return 1;
		
	return 0;
	
}

int comparar_min (const int *clave1, const int *clave2){
	
	if (!clave1 || !clave2)
		return 0;
	
	if (*clave1>*clave2)
		return -1;
		
	if (*clave1<*clave2)
		return 1;
		
	return 0;

}



void prueba_heap_insertar()
{
	/* HEAP DE MAXIMOS */
	cmp_func_t cmp = (cmp_func_t) comparar_max;
	heap_t* heap = heap_crear(cmp);
	
	int* valor1 =malloc(sizeof(int));
	int* valor2 =malloc(sizeof(int));
	int* valor3 =malloc(sizeof(int));
	int* valor4 =malloc(sizeof(int));
	int* valor5 =malloc(sizeof(int));
	int* valor6 =malloc(sizeof(int));
	
	*valor1 = 4;
	*valor2 = 9;
	*valor3 = 13;
	*valor4 = 18;
	*valor5 = 25;
	*valor6 = 30;
	
	
	
	/* Inserta 6 valores desordenados */
	print_test("Prueba heap insertar valor3", heap_encolar(heap, valor3));
	print_test("Prueba heap la cantidad de elementos es 1", heap_cantidad(heap) == 1);
	print_test("Prueba heap ver max es valor3", heap_ver_max(heap) == valor3);
	print_test("Prueba heap ver max es valor3", heap_ver_max(heap) == valor3);
	
	print_test("Prueba heap insertar valor2", heap_encolar(heap, valor2));
	print_test("Prueba heap la cantidad de elementos es 2", heap_cantidad(heap) == 2);
	print_test("Prueba heap ver max es valor3", heap_ver_max(heap) == valor3);
	print_test("Prueba heap ver max es valor3", heap_ver_max(heap) == valor3);

	print_test("Prueba heap insertar valor4", heap_encolar(heap, valor4));
	print_test("Prueba heap la cantidad de elementos es 3", heap_cantidad(heap) == 3);
	print_test("Prueba heap ver max es valor4", heap_ver_max(heap) == valor4);
	print_test("Prueba heap ver max es valor4", heap_ver_max(heap) == valor4);
	
	print_test("Prueba heap insertar valor1", heap_encolar(heap, valor1));
	print_test("Prueba heap la cantidad de elementos es 4", heap_cantidad(heap) == 4);
	print_test("Prueba heap ver max es valor4", heap_ver_max(heap) == valor4);
	print_test("Prueba heap ver max es valor4", heap_ver_max(heap) == valor4);
	
	print_test("Prueba heap insertar valor6", heap_encolar(heap, valor6));
	print_test("Prueba heap la cantidad de elementos es 5", heap_cantidad(heap) == 5);
	print_test("Prueba heap ver max es valor6", heap_ver_max(heap) == valor6);
	print_test("Prueba heap ver max es valor6", heap_ver_max(heap) == valor6);
	
	print_test("Prueba heap insertar valor5", heap_encolar(heap, valor5));
	print_test("Prueba heap la cantidad de elementos es 6", heap_cantidad(heap) == 6);
	print_test("Prueba heap ver max es valor6", heap_ver_max(heap) == valor6);
	print_test("Prueba heap ver max es valor6", heap_ver_max(heap) == valor6);
	
	heap_destruir(heap,free);
	
		
}

	
void prueba_heap_borrar (){	

	/* HEAP DE MAXIMOS */
	cmp_func_t cmp = (cmp_func_t) comparar_max;
	heap_t* heap = heap_crear(cmp);
	
	int* valor1 =malloc(sizeof(int));
	int* valor2 =malloc(sizeof(int));
	int* valor3 =malloc(sizeof(int));
	int* valor4 =malloc(sizeof(int));
	int* valor5 =malloc(sizeof(int));
	int* valor6 =malloc(sizeof(int));
	
	*valor1 = 4;
	*valor2 = 9;
	*valor3 = 13;
	*valor4 = 18;
	*valor5 = 25;
	*valor6 = 30;
	
	/* Inserta 6 valores desordenados y borro valores en el medio */
	print_test("Prueba heap insertar valor3", heap_encolar(heap, valor3));
	print_test("Prueba heap la cantidad de elementos es 1", heap_cantidad(heap) == 1);
	print_test("Prueba heap ver max es valor3", heap_ver_max(heap) == valor3);
	print_test("Prueba heap ver max es valor3", heap_ver_max(heap) == valor3);
	
	print_test("Prueba heap insertar valor2", heap_encolar(heap, valor2));
	print_test("Prueba heap la cantidad de elementos es 2", heap_cantidad(heap) == 2);
	print_test("Prueba heap ver max es valor3", heap_ver_max(heap) == valor3);
	print_test("Prueba heap ver max es valor3", heap_ver_max(heap) == valor3);
	
	print_test("Prueba heap borrar es valor3", heap_desencolar(heap) == valor3);
	print_test("Prueba heap la cantidad de elementos es 1",heap_cantidad(heap) == 1);
	print_test("Prueba heap ver max es valor2", heap_ver_max(heap) == valor2);
	print_test("Prueba heap ver max es valor2", heap_ver_max(heap) == valor2);
	free (valor3);

	print_test("Prueba heap insertar valor4", heap_encolar(heap, valor4));
	print_test("Prueba heap la cantidad de elementos es 2", heap_cantidad(heap) == 2);
	print_test("Prueba heap ver max es valor4", heap_ver_max(heap) == valor4);
	print_test("Prueba heap ver max es valor4", heap_ver_max(heap) == valor4);
	
	print_test("Prueba heap insertar valor1", heap_encolar(heap, valor1));
	print_test("Prueba heap la cantidad de elementos es 3", heap_cantidad(heap) == 3);
	print_test("Prueba heap ver max es valor4", heap_ver_max(heap) == valor4);
	print_test("Prueba heap ver max es valor4", heap_ver_max(heap) == valor4);
	
	print_test("Prueba heap borrar es valor4", heap_desencolar(heap) == valor4);
	print_test("Prueba heap la cantidad de elementos es 2",heap_cantidad(heap) == 2);
	print_test("Prueba heap ver max es valor2", heap_ver_max(heap) == valor2);
	print_test("Prueba heap ver max es valor2", heap_ver_max(heap) == valor2);
	free (valor4);
	
	print_test("Prueba heap borrar es valor2", heap_desencolar(heap) == valor2);
	print_test("Prueba heap la cantidad de elementos es 1",heap_cantidad(heap) == 1);
	print_test("Prueba heap ver max es valor1", heap_ver_max(heap) == valor1);
	print_test("Prueba heap ver max es valor1", heap_ver_max(heap) == valor1);
	free (valor2);
	
	print_test("Prueba heap borrar es valor1", heap_desencolar(heap) == valor1);
	print_test("Prueba heap la cantidad de elementos es 0",heap_cantidad(heap) == 0);
	print_test("Prueba heap ver max es NULL", heap_ver_max(heap) == NULL);
	print_test("Prueba heap ver max es NULL", heap_ver_max(heap) == NULL);
	free (valor1);
	
	print_test("Prueba heap insertar valor6", heap_encolar(heap, valor6));
	print_test("Prueba heap la cantidad de elementos es 1", heap_cantidad(heap) == 1);
	print_test("Prueba heap ver max es valor6", heap_ver_max(heap) == valor6);
	print_test("Prueba heap ver max es valor6", heap_ver_max(heap) == valor6);
	
	print_test("Prueba heap insertar valor5", heap_encolar(heap, valor5));
	print_test("Prueba heap la cantidad de elementos es 2", heap_cantidad(heap) == 2);
	print_test("Prueba heap ver max es valor6", heap_ver_max(heap) == valor6);
	print_test("Prueba heap ver max es valor6", heap_ver_max(heap) == valor6);
	
	print_test("Prueba heap borrar es valor6", heap_desencolar(heap) == valor6);
	print_test("Prueba heap la cantidad de elementos es 1",heap_cantidad(heap) == 1);
	print_test("Prueba heap ver max es valor5", heap_ver_max(heap) == valor5);
	print_test("Prueba heap ver max es valor5", heap_ver_max(heap) == valor5);
	free (valor6);
	
	heap_destruir(heap,free);

}

void swap_int (int* e1, int* e2){
	int aux = *e1;
	*e1 = *e2;
	*e2 = aux;
	
}

void prueba_heap_volumen (size_t largo,bool debug){
	
	cmp_func_t cmp = (cmp_func_t) comparar_min;
	heap_t* heap = heap_crear (cmp);
	
	int *datos_desordenados = malloc (largo * sizeof(int));
	int *datos_ordenados = malloc (largo * sizeof (int));
	
	/* genero los vectores */
	for (int i = 0; i<largo; i++){ 
		datos_ordenados[i] = i;
		datos_desordenados[i] = i;
	}
	
	for (int i =largo-1; i>0 ; i--){
		int randpos = rand () % i;
		swap_int (&datos_desordenados[randpos],&datos_desordenados[i]);
	}
	
	bool ok = true;
	for (int i = 0; i<largo;i++){
		ok = heap_encolar (heap,&datos_ordenados[i]);
		if (!ok) break;
	}
	
	if (debug) print_test("Prueba heap encolar muchos elementos", ok);
	if (debug) print_test("Prueba heap la cantidad de elementos es correcta", heap_cantidad(heap) == largo);
	
	ok = true;
	
	for (int i = 0; i<largo ;i++){
		ok = (datos_ordenados[i] == *(int*)heap_ver_max(heap));
		if (!ok) break;
		ok = (datos_ordenados[i] == *(int*)heap_desencolar(heap));
		if (!ok) break;
	}
	
	if (debug) print_test("Prueba heap desencolar y ver max muchos elementos", ok);
	if (debug) print_test("Prueba heap la cantidad de elementos es correcta", heap_cantidad(heap) == 0);
	
	
	free (datos_ordenados);
	free (datos_desordenados);
	heap_destruir (heap, NULL);
	
	
	
}	


void prueba_heapsort (int largo,bool debug){
	
	int **datos_desordenados = malloc (largo * sizeof(int*));
	int **datos_ordenados = malloc (largo * sizeof (int*));
	
	/* genero los vectores */
	for (int i = 0; i<largo; i++){ 
		datos_ordenados[i] = malloc (sizeof(int));
		*datos_ordenados[i] = i;
		datos_desordenados[i] = malloc (sizeof(int));
		*datos_desordenados[i] = i;
	}
	
	for (int i = largo-1; i>0 ; i--){
		int randpos = rand () % i;
		swap_int (datos_desordenados[randpos],datos_desordenados[i]);
	}
	
	cmp_func_t cmp = (cmp_func_t)comparar_max;
	
	heapsort ((void**)datos_desordenados,largo,cmp);
	
	bool ok = true;
	for (int i = 0; i<largo; i++){
		ok = (*datos_desordenados[i] == *datos_ordenados[i]);
		if (!ok){
			break;
		}
	}
	
	if (debug) print_test ("Prueba heapsort es OK",ok);
	
	for (int i = 0; i<largo; i++){
		free (datos_ordenados[i]);
		free (datos_desordenados[i]);
	}
	
	free (datos_ordenados);
	free (datos_desordenados);
	
	
}


/* ******************************************************************
 *                        PROGRAMA PRINCIPAL
 * *****************************************************************/

/* Programa principal. */
int main(int argc, char** argv){

	if (argc < 2) {
	    /* Ejecuta todas las pruebas unitarias. */
    	prueba_crear_heap_vacio();
	prueba_heap_insertar();
	prueba_heap_borrar();
	prueba_heap_volumen(5000, true);
	prueba_heapsort (5000,true);
		
	} else {
		size_t largo = atoi(argv[1]);
		prueba_heap_volumen(largo, false);
		
		
	}
    return 0;
}







